МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління
Лабораторна робота №1-2 з дисципліни “Математичні методи дослідження операцій” на тему «Постановка задачі лінійного програмування та її розв’язання графічним методом» Мета роботи: набуття навиків побудови математичної моделі задачі лінійного програмування, вивчення графічного методу для знаходження розв’язку системи нерівностей, навчитися використовувати графічний метод застосовуючи готові пакети програм ( MS Exel, MathCad та ін. ) і на основі отриманих знань створити власну програму на одній із вже вивчених мов програмування. 1. Короткі теоретичні відомості: Суть графічного методу розв’язання системи лінійних нерівностей. Задача знаходження розв'язку системи лінійних нерівностей відіграє важливу роль у розв'язуванні багатьох задач математичного програмування, а не лише лінійного. Ця задача має і самостійний інтерес. Розглянемо спочатку такий приклад. Нехай дано систему нерівностей:
(2) Геометрично кожну нерівність системи (2) можна тлумачити як деяку півплощину, обмежену прямою, рівняння якої можна дістати з відповідної нерівності, змінивши знак нерівності знаком рівності. Через di(x1, x2) (і =1, 2, ..., 6) позначено відхилення довільної точки з координатами x1, x2 від відповідної прямої. Так, відхилення точки з координатами х1=3, х2 = 8 від прямої d1(x1, x2) = -1х1 - 1х2 + 11 = 0 становить d1(3, 8) = -1*3 - 1*8 + 11 = 0, тобто точка (3; 8) лежить на цій прямій; аналогічно знаходимо відхилення точки (3; 8) від прямої d2(x1, x2), яке становить -3; від прямої d3(x1, x2) становить 15 і т.д. У точці з координатами (x1; x2) нерівність, наприклад, d1(x1, x2) = -1х1 - 1х2 + 11 = 0, виконується, якщо відхилення такої точки від прямої d1(x1, x2) = -1х1 - 1х2 + 11 = 0 невід'ємне.
Рис.6. На Рис. 6 зображено множину точок W (її заштриховано), у кожній точці якої винонуються всі нерівності системи (2). Отже, множина W є множиною розв'язків системи нерівностей (2). Якщо точка х належить множині W розв'язків системи нерівностей (2), то відхилення цієї точки від усіх прямих, які обмежують множину W, будуть невід'ємними. А якщо точка не належить W, то принаймі одна з нерівностей не справджуватиметься і координати цієї точки не задовольнятимуть систему нерівностей, які визначають множину W. Очевидно, W є опуклим многокутником. Отже, якщо всі відхилення деякої точки від прямих, що обмежують множину W, невід'ємні, то набір координат такої точки є одним із розв'язків даної системи нерівностей. Такий розв'язок називатимемо допустимим. Точку, що відповідає допустимому розв'язку, називатимемо допустимою. Як бачимо, у двовимірному просторі задачу можна розв'язати графічним способом, побудувавши множину розв'язків для кожної нерівності і взявши переріз таких множин. Якщо цим перерізом є порожня множина, то система нерівностей несумісна. Опис програм MS Exel і MathCad. Програма MS Exel. MS Excel - є програмою для розрахунків за допомогою електронних таблиць. Головна область її застосування - виконання розрахунків, як в бізнесі так і у повсякденному житті. Excel має велику кількість вбудованих функцій, різні засоби обробки даних, багато сервісних засобів, мета яких полегшити роботу користувачеві. При завантаженні Excel автоматично відкривається нова пуста робоча книга. Робоча книга складається з 16 робочих таблиць (розмір кожної 256 колонок та 16384 рядки).Розглянемо вікно програми Excel. Перша панель у вікні Excel - панель заголовку. Вона показує ім’я програми та ім’я файлу. Ліворуч знаходиться кнопка системного меню, праворуч - кнопки зміни розміру вікна. Друга панель - панель меню. Вона містить у собі спадні меню, яки використовують для вибору різних команд Excel. File (файл) - дозволяє оперувати файлами, тобто створення нової робочої книги, відкриття вже існуючої, запис, закриття файлу, пошук, встановлення параметрів сторінок для роздруку робочих листів, ...